﻿//LCR114.火星词典(hard): https://leetcode.cn/problems/Jf1JuT/description/
class Solution {
public:
    unordered_map<char,vector<char>> edges;
    unordered_map<char,int> in;  //入度
    string alienOrder(vector<string>& words) {
        for(auto word:words)
        {
            for(auto ch:word)
            {
                in[ch]=0;
            }
        }
        //建图
        int n=words.size();
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
            {
                if(!Compare(words[i],words[j]))  return "";
            }
        }
        queue<char> q;
        string ret;
        //拓扑排序
        for(auto& e:in)
        {
            if(e.second==0) q.push(e.first); 
        }
        while(q.size())
        {
            auto ch=q.front(); q.pop();
            ret+=ch;
            for(char x:edges[ch])
            {
                in[x]--;
                if(in[x]==0)  q.push(x);
            }
        }
        //看是否有环
        for(auto& e:in)
        {
            if(e.second!=0)  return "";
        }
        return ret;
    }
    bool Compare(string& s1,string& s2)
    {
        int cur1=0,cur2=0;
        int n1=s1.size(),n2=s2.size();
        while(cur1<n1&&cur2<n2)
        {
            char x1=s1[cur1];
            char x2=s2[cur2];
            if(x1!=x2)
            {
                if(find(edges[x1].begin(),edges[x1].end(),x2)==edges[x1].end())  
                {
                    edges[x1].push_back(x2);
                    in[x2]++;
                }
                return true;
            }
            cur1++,cur2++;
        }
        //abc ab  错误         | ab ab | a ab   正确
        return s1.size()<=s2.size();
    }

};